import java.io.IOException;
import java.util.*;


/*
 *  Greg Schevach, Christopher Nerf, Mesfin Solomon, Vidat Muslim
 *  Project 2: Huffman Tree
 *  	Purpose: Read in data from a file, count instances of each letter
 *  			 create a way to store and sort letters, use storage device to create huffman tree
 * 
 */

public class Project2 
{
	//gonna use a single linked list to count the instances

	@SuppressWarnings("unchecked")
	public static void main( String [] args) throws EmptyDequeException
	{

		//need this to read in the files
		CharReader mf = new CharReader("C:\\Users\\nerfc\\Desktop\\test.txt");
		//this is going to be my linked list
		LinkedList ll = new LinkedList();
		boolean EOF = false;

		while (!EOF)
		{
			
				//here we are going to look through the entire linked list
				//and check to see if the value of 'nodeVal' already exists
				//if it does, we increase that nodes value by 1
				//if it doesnt, we check the next node
				//if the next node is false, we switch the notPresent flag to true
				//add the node, then break out of the loop
				boolean present = false;
				Node n = null;
				int nodeVal = 0;
				try{
					nodeVal = mf.readNextChar();
				}
				catch (Exception wtf)
				{
					EOF = true;
				}
				if(EOF || nodeVal == -1)
					break;
				
				if(ll.isEmpty())
				{
					ll.addRear(nodeVal);
				}
				else
				{

					n = ll.getFrontNode();
					do
					{
						
						int element = (Integer)n.getElement();
						if(element == nodeVal)
						{
							n.increaseCount();
							present = true;
						}
						else
							n = n.getnextLeft();

						if(n == null)
						{
							ll.addRear(nodeVal);
							present = true;
						}
					} while(!present);

				}
		}	
		//debug printing
		//ll.print();
		
		//time to sort!
		
		ll.sortList();
		ll.print();
		LinkedList q = ll;
		
		String location = "";
		Node tn;
		Node tn2;
		Node newtree = new Node();
		//gonna remove everything from the linked list and enqueue it into a queue
		
		MyDeque mdq = new MyDeque();
		MyDeque codedq = new MyDeque();
		
		mdq.addLast(newtree);
		codedq.addLast(location);
		
		//MyDeque valdq = new MyDeque();
		for(Node n = q.getFrontNode(); n != null; n = n.getnextLeft())
		{
			mdq.addFirst(n);
			//valdq.addFirst(n.getCount());
		}
		
		while(!(mdq.size() == 1))
		{

			Node intNode = new Node();
			
			try{
				Node n = (Node)mdq.removeFirst();
				n.setnextLeft(null);
				n.setnextRight(null);
				tn = n;
				intNode.setnextLeft(tn);}
				catch(Exception wtf){}
			
				try{
					Node n = (Node)mdq.removeFirst();
					n.setnextLeft(null);
					n.setnextRight(null);
					tn2 = n;
					intNode.setnextRight(tn2);}
		catch(Exception wtf){}
			
			mdq.addLast(intNode);
			//location = (String)codedq.removeFirst();
			
		}
		
		Node t = (Node)mdq.removeLast();
		Tree baum = new Tree(t);
		
		baum.printTree(baum.head);
		
		System.out.println((t.getnextLeft()).getElement());
		System.out.println((t.getnextRight()).getElement());
		
		//System.out.print("mdq\n" + mdq.toString());
		//System.out.println("valdq\n" + valdq.toString());
		
		
		
		
					
		//time to try to create a HuffmanTree
		DoubleNode tree = new DoubleNode();
		//create a head varaible to point at the head of the tree
		DoubleNode head = tree;
		//this is the value of the head in the tree
		String huffmanCode = "1";
		//set it thusly
		tree.setHuffmanCode(huffmanCode);	
		
		
		
		for(Node next = ll.getHeadNode(); next != null; next = next.getnextLeft())
		{
			
			//create the node that will be the left node
			DoubleNode Left = new DoubleNode();
			//set the left element to the value that is currently in next
			Left.setElement(((Integer)next.getElement()).toString());
			//add 0 to the huffman code prior to setting it to the left value
			String LeftCode = huffmanCode.concat("0");
			//set the left huffman code
			Left.setHuffmanCode(LeftCode);
			//set the the value of the left point node
			tree.setNextLeft(Left);
			//permanently add 1 to the huffmancode
			huffmanCode = huffmanCode.concat("1");
			//create a right node
			DoubleNode Right = new DoubleNode();
			//set the right node's huffman code to the new huffmancode
			Right.setHuffmanCode(huffmanCode);
			//set tree.right = Right
			tree.setNextRight(Right);
			//set tree = right
			tree = tree.getNextRight();
			
		}
		
		//print everything in the tree
		head.print(head);
		
		//above is wrong, need to fix that, right?
		/*
		 * Start with as many leaves as there are symbols.
Enqueue all leaf nodes into the first queue (by probability in increasing order so that the least likely item is in the head of the queue).
While there is more than one node in the queues:
Dequeue the two nodes with the lowest weight by examining the fronts of both queues.
Create a new internal node, with the two just-removed nodes as children (either node can be either child) and the sum of their weights as the new weight.
Enqueue the new node into the rear of the second queue.
The remaining node is the root node; the tree has now been generated.
		 */
		
		
		
		
	}
	
	
}




